COMMENT ⊗   VALID 00006 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	.NEWSEC RUNTIME SYSTEM
C00009 00003	.NEWSS (PHILOSOPHY OF SERVOING,SERVOING)
C00018 00004	.NEWSS	(TRAJECTORIES,TRAJECTORIES)
C00021 00005	.NEWSS INTERPRETABLE CODE
C00029 00006	.gpa:NEWSS(ALGORITHMS FOR USE OF GRAPH STRUCTURE,GRAPH ALGORITHMS)
C00032 ENDMK
C⊗;
.NEWSEC RUNTIME SYSTEM

	This appendix discusses in greater detail some of the aspects
of the runtime system, which resides on the PDP11 as a set of programs
executing compiled code, operating devices in real time and receiving
sensory input.

.NEWSS (THE RUNTIME SCHEDULER,THE SCHEDULER)

	As mentioned earlier, in chapter 7, the runtime scheduling is
managed  through  a  combination  of  priority  level assignments  to
various types  of  processes  and  a time-slot  request  list.
The  PDP-11 hardware provides eight processor priority levels.  These
are assigned in the HAL system as follows:
.BEGIN
.TABBREAK
.PREFACE 0
.NARROW 8,8
	7. AD (Analog-to-digital converter), joint servoing
	6. Clock, calendar
	5. <spare>
	4. ON condition checkers; Interrupt handlers for
	various condition-checking devices (eg finger pads).
	3. servo predictor
	2. <spare>
	1. Interpreters, scheduler for background stuff.
	0. Interpreters
.END

	 The HAL system keeps a calendar of  things that must be done
in each time interval.  With time slot is associated:
.BEGIN
.TABBREAK
.PREFACE 0
.NARROW 8,8
	a. An AD command list which is to be started.
	b. A queue of procedure calls to make at various priority
levels.
.END

	  When the  clock ticks, the  clock interrupt  routine starts
running in kernel  mode.   The first thing  it does is  to start  the
specified AD  command list,   if  any.  (This  will cause  an AD-done
interrupt  in  around  20-30 microseconds.)  Finally,    it  uses the
software interrupts to arrange for all of the  queued procedure calls
to take place at the appropriate levels.

	The AD service routine  runs at priority level 7, and
uses register set zero.   However,  it does run  in user mode,   thus
safeguarding the rest of  the system from bugs.  The  AD command list
consists of a sequential table of two word entries:
.BEGIN TABBREAK NARROW 8,8; PREFACE 0;
	a. CHNCMD -- channel command
	b. SAMPLE -- usually, a slot for storing a sample value.
.END

	Essentially,  the   AD  service  routine  keeps  an  internal
variable that points to the  entry in the command list  corresponding
to the most recent (current)  AD channel command.  When an AD-done
interrupt occurs,   the service routine copies the contents of the AD
value register into the current SAMPLE slot.  It  then increments its
pointer to  point at the next two  word entry.  If CHNCMD  of the new
entry is non-zero,  it issues the appropriate command and  dismisses.
If CHNCMD is zero, then  SAMPLE is assumed to be the  address of some
code  to be executed (typically,   a servo).   In this case,   the AD
service routine will just clear its internal pointer (to signify that
it is done), and jump to the indicated address.

	Typically,  a servoing operation  will have two "phases", one
which  runs at level 7 as a response  to an AD-done interrupt and which is
responsible for emitting the new drive, and a somewhat lower priority
one  which requests  a  new time  slot from  the  calendar management
routine and  sets up  the correction  phase  for the  new slot.    As
previously indicated,  this first phase  is "scheduled" by  putting a
pointer to the appropriate AD command list into the "AD request" part
of a calendar  time slot.   The second phase  is scheduled merely  by
entering it onto the calendar queue  of things to be requested in the
same tick.  Joint servos are described more fully in the next section.

	If  a non-critical  process (eg,   an  ON-monitor)  needs a
"consistent" set of  AD measurements, it can  get them by setting  up
the appropriate AD  command list, finding a time  slot for taking the
measurements, and then placing a request that the computation that is
to use the set of  measurements be started up at the  time slot after
the one in which the measurements are made.  

	In  cases where a command  list is too long  to be finished in
one time slot, the  process requesting the measurements must  reserve
two (or more) contiguous slots.   This is done by placing the command
list id  in the first slot and a special flag value (perhaps -1) into
the remaining slots, so that  no other processes will try  to reserve
them.

.NEWSS (PHILOSOPHY OF SERVOING,SERVOING)

	Control of the manipulators is  entirely within the computer.
Position,  velocity  and force information are read into the computer
and motor drive level is output by the computer at whatever  rate the
servo can accomplish.

	The control of manipulators could be analog but even in
the  simplest mode of operation,  position  servoing, it is necessary to
consider coordinated  motion of  all  six joints  along a  trajectory
defined by  a sequence of polynomials.   In performing  tasks, such a
screwing in screws, motion is  more complex, involving a  combination
of  position,  velocity  and force  servoing;  the  mode  changes  in
response  to external and  internal stimuli.   Even if  many modes of
analog servoing were provided it  would still be necessary to  inform
the computer of all the servo information in order for it to interact
correctly.   We close  all servo  loops within  the computer
itself and use no analog servos at all. Closing the servo loop in the
computer requires very  little additional computation as the computer
must essentially perform a servo calculation in order to decide 
which servo mode to use and what set point to output.

	The limitations imposed  by use of the computer  for servoing
are bandwidth  and the noise of digitizing. The computer  servo is a sampled
data system  of quite  low sample  rate.   These  limitations can  be
corrected,  in part, by providing high frequency velocity feedback in
analog form, without affecting the computer servo.

.NEWSS (JOINT SERVOING,SERVOING)

	Any coordinated  motion of the  arm can  be expressed as  six
time dependent motions, one for each joint; the coordinated motion is
parameterized in terms of time.  The problem of servoing the arm,  or
arms, is  thus reduced to  a problem of  servoing a number  of joints
with respect to time.

	A joint  servo has two  parts: a drive  part and  a predictor
part. As mentioned  before, the drive part is run at priority level 7.
When  it  finishes,  the  servo  enters  priority  level  3  for  the
predictor. First, the  predictor reserves a time for the  next run of
this  servo. The  delay is  chosen based  on considerations  of joint
response time, joint velocity, and availability of time slots.

	Now the  predictor evaluates  the motion  polynomial for  the
time which it has reserved.  This evaluation may take into account an
interpolating   polynomial    used   for    last-minute    trajectory
modification, as well  as any offset  that might be necessary  due to
modifications being made during the motion itself. These calculations
give  the  predicted   set  point.     The  predicted  velocity   and
acceleration are  obtained by  difference techniques based  on recent
set  point values.  The  joint inertia and  gravity force loading are
interpolated.  The  gravity loading  is added to  the product of  the
predicted  acceleration and the  joint inertia  to yield  a predicted
drive.

	If this joint has multiple wipers then the appropriate  wiper
to read the joint position is determined.  Then the joint calibration
is  applied to  the  set point  to yield  the  expected potentiometer
reading for the joint  at the reserved  time. The servo gains,  which
are dependent on joint inertia,  are next calculated, and finally the
servo equation is set up in terms of observed position and velocity.
	The  form of the  servo equation is dependent  on whether the
joint  is being  run  with  position, velocity,  or  force  servoing.
Having  done all  this  predictive work,  the  joint servo  dismisses
control.

	When the reserved time  occurs, the drive  part of the  servo
runs in priority  level 7. The  drive part measures the  position and
velocity,   evaluates the  servo equation prepared  by the predictor,
applies friction compensation  and drives the joint.  This is a  very
fast  computation and  minimizes  any delay  between observation  and
action.  The   predictor  is  then  run  again  for  the  next  servo
scheduling, as described above.

	Upon completion of the motion, or if some error should occur,
or  if some other  process requests  that the joint  stop, completion
codes are set for the joint, and then the servo terminates.

	The advantage of this servo scheme is that it allows flexible
scheduling: each joint can  run at its own required  repetition rate.
As  the joint  knows  when it  will  be run  next it  is  possible to
pre-compute most of the drive and thus reduce the servo delay.

	Each servo routine has a control block which includes a status
register. In the
case  of a  joint servo  the status  register contains  the following
bits:
.UNFILL;
	RUN		joint is running or about to be run
	FIRST		first time through loop for this motion.
	FINAL		in final state, nulling errors
	STOP		stop this joint, or joint is stopped
	EXFORCE		joint stopped due to excessive force.
	ADERR		a/d error
	NONEX		joint is down or does not exist
	STERR		servo was not run on schedule
	SERVO		position servo
	VELS		velocity servo
	FORCE		exert force
	WOB		perturb this joint while running
	NUL		null errors at end and stop
.REFILL

	When the servo is started up for the  first time, it is given
certain information,  including which  joint it should
servo, what  the properties  of that  joint are,  what polynomial  to
follow, the predicted gravity torque and inertia loadings.
.NEWSS	(TRAJECTORIES,TRAJECTORIES)

	A trajectory for the hand is generated at compile time
under the assumption that the planning values for
the  initial point,  departure  point, via  points,
arrival  point and  final  position  are accurate.

	If at  run time it is found that some or all of these planned
positions have  moved slightly  it  becomes necessary  to modify  the
planned  trajectory to  pass through  the actual  positions.   If the
actual  positions  are  only  slightly  different  from  the  planned
positions then the  trajectory is still  almost optimal, that  is, it
still has most of  the properties with which it was designed.  If the
deviation from the planned  values to the  actual are great then  the
trajectory is  no longer  optimal.   To plan  a new  trajectory would
again optimize the move, but only if the time to compute is less than
the time saved  is it worth recomputing.  At present this is  not the
case,  so no  recalculation of  trajectories is  done.   Instead, the
following trajectory modification step is performed:

	Before the move is executed, it is prepared by computing  the
discrepancies between actual locations and  planned locations.  Fifth
degree  interpolating   polynomials  (with  zero  initial  and  final
velocity and acceleration) are computed to be added into  the planned
polynomials to bring  the planned trajectory into  line with reality.
The  joint angles associated with  a frame are  stored along with its
matrix, so this often  does not involve much calculation,  unless the
frame has been changed  since these calculations were done last. Also
at this time the joint  inertias and gravity loadings are  calculated
and stored in the value cell of relevant frames.

.NEWSS INTERPRETABLE CODE

	The basic instruction  emitted by the compiler is  one 16-bit
word.   The first 8 bits are  the opcode, and the last  8 are used to
form the operand address, if the opcode needs one.   Addressing modes
are either immediate, in which case the next word has the address, or
relative (to the program counter).  Immediate addressing is indicated
by the second  byte being 0.   Anything else is relative  addressing;
bit 8  (the lefthand bit of  the righthand byte) is a  sign bit; thus
one can look 127 locations forward or backward; the full word address
will be  found at this  place.  Full-word  addresses can  be indirect;
this  is  indicated  by  a  high-order  bit  (ie,  bit  0)  being  1.
Indirection can proceed to any level.
.SKIP SPREAD
←STACK OPERATORS
.BEGIN INDENT 0,16
.PREFACE 0

pushadr <arg>	\puts <arg> on top of the stack.  It is assumed that
		  <arg> is the address of a variable.

pushval <arg>	\puts value of variable pointed to by <arg> on stack.
		  gets good value, if necessary.

pop		\pops the stack.

copy <num>	\finds the <num>'th element down in the stack, and copies
			it to the top.

flush		\clears the stack.

store <arg>    	\pointer at top of stack copied into value pointer at <arg>;
		  stack is popped.
.END

←SINGLE FRAME OPERATIONS
.BEGIN INDENT 0,16
.PREFACE 0

solve		\takes a pointer to a frame value cell from top of stack.
		  Generates arm solution (if necessary) and stores in the
		  value cell.  The stack is popped.

invert		\the inverse of the value cell at top of stack goes to
		  top of stack; old top popped.
.END

←ARITHMETIC

	For the  following, the  args are  on the  stack, are  popped
after the  operation, the answer pointed to  on top of stack. Earlier
arguments deeper on the stack.
.BEGIN INDENT 0,16
.PREFACE 0

s+s		\scalar addition.  2 args.

s-s		\scalar subtraction.  2 args.

s*s		\scalar multiplication.  2. args.

s/s		\scalar division.  error if second arg is 0.  2 args.

|v|		\magnitude of vector.  1 arg.

v.v		\dot product.  returns scalar.

(sss)		\forms vector from 3 scalars.  3 args.

s*v		\dilation of vector.  2 args.  scalar first.

v+v		\vector addition.  2 args.

vα∂v		\vector rotated by vector.  second arg is rotation.  2 args.

t*v		\transformation of vector.  trans first.  2 args.

[v:v]		\forms frame from 2 vectors.  first is loc, second orient.

f+v		\translation of frame.  2 args.  frame first.

fα∂v		\rotation of frame.  2 args.  frame first.

t*f		\transformation of frame.  2 args.  frame first.

fα→f		\forms trans from two frames.  2 args.  f1'f2.

[v|v]		\forms trans from two vectors.  1: trans; 2: rot.

t+v		\translates trans.  2 args.  trans first.

tα∂v		\rotates trans.  2 args.  trans first.

t*t		\composition (to the left) of two transes.

tinv		\inverse of trans
.END

←EXTRACTION AND COMPOSITION
.BEGIN INDENT 0,16
.PREFACE 0

loc		\location of frame replaces it at top of stack.

orient		\orientation of frame replaces it at top of stack.

xscal		\x coordinate of vector replaces it at top of stack.

yscal		\y coordinate of vector replaces it at top of stack.

zscal		\z coordinate of vector replaces it at top of stack.
.END

←PROCESS CONTROL
.BEGIN INDENT 0,16
.PREFACE 0

sprout <arg>	\start up an interpreter with program counter <arg>.

enable <arg>	\start up an on-monitor with location of status word <arg>.

disable <arg>	\the on-monitor with location of status word <arg> is disabled.

wait		\wait until all descendant (non on-monitor) processes are dead.
		  Then kill descendant move on-monitors and continue.

terminate	\terminate this process.  Should first call "wait".
.END

←JUMPS
.BEGIN INDENT 0,16
.PREFACE 0

This list is not complete.

jump <arg>

nop		\no-op.
.END

←ARM AND DEVICE CONTROL
.BEGIN INDENT 0,16
.PREFACE 0

prepmove <arg>	\<arg> points to the move vector.  Trajectory modification
		  happens now.

startmove	\sprouts joint servos and move-monitors

search <arg>	\<arg> points to the search vector.

stop <arg>	\<arg> encoding of what devices must be stopped.
.END

←INPUT AND OUTPUT
	Some sort of I/O will be implemented, most likely including string
output to the supervisor, error message output, and input (from supervisor
or from coresident routines) of value cells.

←DEBUGGING AIDS
.BEGIN INDENT 0,16
.PREFACE 0

source <arg>	\notes that <arg> is where the interpreter is now in
		  source code.

tellsource	\output current source location to the 10.

step		\begins step mode, which does one interpretation at a time,
		  requires message to continue.

offstep		\turns off step mode; normal speed is resumed.
.END
.gpa:NEWSS(ALGORITHMS FOR USE OF GRAPH STRUCTURE,GRAPH ALGORITHMS)

These are the algorithms used to find values for variables in the
graph structure and to change those values.

.UNFILL
PROCEDURE invalidate (POINTER(NODE) n);
	IF invmark(n)=0 THEN
		BEGIN  COMMENT:  This cell currently marked valid;
		POINTER p;
		invmark(n)α← -1;
		p α← dependents(n);
		WHILE p%7≠%*NULL DO
			BEGIN  COMMENT: Mark all dependents as invalid;
			invalidate(p);
			p α← link(p)
			END
		END;

.REFILL

.UNFILL
PROCEDURE change (POINTER(NODE) n; POINTER(VALUE) vnew);
	BEGIN
	COMMENT:  This procedure is called in order to explicitly assign
		a new value, vnew, to node n;
	POINTER(VALUE) vold;
	invalidate(n);
	vold α← value(n);
	value(n)α←vnew;
	p α← changer(n);
	WHILE p%7≠%*NULL DO
		BEGIN  COMMENT:  Handle all changers;
		APPLY(code(p),vold,vnew);
		p α← link(p);
		END;
	invmark(n) α← 0;
	END;

.REFILL

.UNFILL
POINTER(VALUE) PROCEDURE getvalue (POINTER(NODE) n);
	BEGIN
	IF invmark(n)%7≠%*0 THEN evalnode(n, time α← time+1);
	RETURN(value(n));
	END;

.REFILL

.UNFILL
PROCEDURE evalnode (POINTER(NODE) n, INTEGER t);
	BEGIN  COMMENT:  Put a good value in the value cell of n.
		t is used to break cycles;
	IF invmark(n)=0 ∨ invmark(n)=t THEN RETURN;
	invmark(n) α← t;
	p α← calculator(n);
	WHILE p %7≠%* NULL DO
		BEGIN "cloop"
		POINTER(node) d;
		d α← needed(p);
		WHILE d %7≠%* NULL DO
			BEGIN
			evalnode(node(d),t);
			IF invmark(dep(d))%7≠%*0 THEN
				BEGIN
				p α← next(p);
				CONTINUE "cloop";
				END;
			d α← next(d);
			END;
		value(n)α←APPLY(code(p), args(p));
		invmark(n)α←0;
		RETURN;
		END;
	END;
.REFILL